//
// Created by 吴竹亚 on 2023/3/25.
//
#include <stdio.h>

typedef struct {
    int no;
    int sco;
} Student;

typedef struct BINTNODE {
    Student data;
    struct BINTNODE *leftChild, *rightChild;
} BINTNODE, *BiTree;

Student *stus = new Student[7];

BiTree createBT(int p, int l) {
    if (p > l) {
        return nullptr;
    }
    BiTree tree = new BINTNODE;
    tree->data = stus[p];
    tree->leftChild = createBT(p * 2, l);
    tree->rightChild = createBT(p * 2 + 1, l);
    return tree;
}

// 先序遍历
void Pre(BiTree &tree) {
    if (tree->data.sco != 0) {
        tree->data.sco += 10;
        if (tree->leftChild != NULL) {
            Pre(tree->leftChild);
        }
        if (tree->rightChild != NULL) {
            Pre(tree->rightChild);
        }
    }
}

// 凹入法显示二叉树
void ShowTree(BiTree t, int l) {
    if (t == NULL) {
        return;
    }
    for (int i = 0; i < l; ++i) {
        printf("▃▃");
    }
    printf("no: %d, score: %d \n", t->data.no, t->data.sco);
    ShowTree(t->leftChild, l + 1);
    ShowTree(t->rightChild, l + 1);
}

// 求叶子节点数量
int leafNum(BiTree tree) {
    if (tree->leftChild == NULL && tree->rightChild == NULL) {
        return 1;
    }
    int n = 0;
    if (tree->leftChild != NULL) {
        n += leafNum(tree->leftChild);
    }
    if (tree->rightChild != NULL) {
        n += leafNum(tree->rightChild);
    }
    return n;
}

// 求节点总数
int nodeNum(BiTree tree) {
    if (tree != NULL) {
        return 1 + nodeNum(tree->rightChild) + nodeNum(tree->leftChild);
    }
    return 0;
}

int treeDepth(BiTree tree) {
    if (tree == nullptr) {
        return 0;
    }
    int left = treeDepth(tree->leftChild) + 1;
    int right = treeDepth(tree->rightChild) + 1;
    if (left > right) {
        return left;
    }
    return right;
}

int main() {
    for (int i = 1; i <= 6; ++i) {
        stus[i].no = i + 43;
        stus[i].sco = i + 10;
    }
    BINTNODE *t = createBT(1, 6);
    ShowTree(t, 1);
    Pre(t);
    printf("==============\n");
    ShowTree(t, 1);
    printf("==============\n");
    int leafnum = leafNum(t);
    printf("叶子节点数量: %d\n", leafnum);
    int nodenum = nodeNum(t);
    printf("节点数量: %d\n", nodenum);
    int depth = treeDepth(t);
    printf("深度: %d\n", depth);
}
